package com.mdnote.structure.search;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/28
 * @description 差值搜索
 */
public class InsertValueSearch {

    public static int search(int[] source, int left, int right, int element) {

        if (left > right || element < source[0] || element > source[source.length - 1]) {
            return -1;
        }
        int mid = left + (right - left) / (source[right] - source[left]) * (element - source[left]);

        if (element < source[mid]) {
            // 左边
            return search(source, left, mid - 1, element);
        } else if (element > source[mid]) {
            // 右边
            return search(source, mid + 1, right, element);
        } else {
            return mid;
        }
    }

    public static void main(String[] args) {
        int[] data = {11, 22, 33, 44, 55, 66};
        System.out.println(search(data, 0, data.length - 1, 33));
    }
}
